#include <iostream>
#include <vector>

using namespace std;
// 234. 回文链表
// 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

/**
 * Definition for singly-linked list.
*/
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
private:
    // 找中间结点
    ListNode* middleNode(ListNode* head) {  // 求中间位置的结点
        ListNode *slow = head;
        ListNode *fast = head;
        while(fast->next != nullptr && fast->next->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    // 翻转不带头结点的单链表head
    ListNode* reverseList(ListNode *head) {
        ListNode *p = head, *q;
        auto *dummyHead = new ListNode(-1); // 建立带头结点的空链表dummyHead
        // 头插法：将p指向的结点插入dummyHead的后面
        while(p != nullptr) {
            q = p->next;
            p->next = dummyHead->next;
            dummyHead->next = p;
            p = q;
        }
        ListNode *retNode = dummyHead->next;
        delete dummyHead;
        return retNode; // 返回翻转后的不带头结点单链表
    }
public:
    bool isPalindrome(ListNode* head) {
        if(head == nullptr) return true;
        if(head->next == nullptr)   // 只有一个结点
            return true;
        if(head->next->next == nullptr) // 只有两个结点
            return head->val == head->next->val;

        ListNode *mid = middleNode(head);
        ListNode* head2 = mid->next;    // 构造后一半结点的单链表

        head2 = reverseList(head2); // 翻转head2

        while(head2 != nullptr) {   // head的结点个数 >= head2的结点个数
            if(head->val != head2->val)
                return false;

            head = head->next;
            head2 = head2->next;
        }

        if(head2 == nullptr)
            return true;
        else
            return false;
    }
};
int main() {
    std::cout << "Hello, World!" << std::endl;
    return 0;
}
